The present invention relates to the field of computer graphics, and in particular to methods and apparatus for optimizing the evaluation of functions associated with surfaces. Many computer graphic images are created by mathematically modeling the interaction of light with a three dimensional scene from a given viewpoint. This process, called rendering, generates a two-dimensional image of the scene from the given viewpoint, and is analogous to taking a photograph of a real-world scene. Animated sequences can be created by rendering a sequence of images of a scene as the scene is gradually changed over time. A great deal of effort has been devoted to making realistic looking rendered images and animations.
Surface attribute functions can define the values of attributes of surfaces in three-dimensional space. Surface attribute functions can be evaluated at any point on the surface to provide corresponding attribute values at that point on the surface. Attributes of surfaces can include optical properties of a surface, such as color, transparency, reflectivity, and refractivity. Attributes can also include visibility or occlusion information; artistically or procedurally generated texture data in one, two, three, or more dimensions; noise functions in one, two, three, or more dimensions, which can be used to procedurally generate or modify other surface attributes; shadow generation information; forces or attributes used for physics, cloth, fluid, or other types of simulations; animation data, which can be used to specify motion of entities associated with a surface point, such as fur or hair; modeling parameters, such as the density of procedurally generated grass applied to a model of a landscape; illumination information, which specifies the amount and direction of light on the surface point from other portions of the scene; and rendering information, such as ray tracing path information or radiosity rendering information. Functions can be relatively simple, such as looking up texture data from a texture map, or very complex, such as the evaluation of complex user-defined shader programs, ray tracing programs, animation or modeling programs, or simulation programs.
An application such as a rendering, animation, or simulation application determines the attribute values of a given surface point by evaluating the associated surface attribute functions. Typically, this evaluation requires the specification of the position of the given surface point using surface coordinates. For attributes values that remain fixed to surface points regardless of the surface's pose (or position, orientation, and shape), attribute values for surface points can be cached or stored. This eliminates redundant evaluations of surface attribute functions and decreases the time required for rendering or other operations utilizing surface point attribute values.
Surfaces for three-dimensional models are defined by mathematical relationships. The mathematics defining some types of surfaces, such as polygons and bicubic patches, have a natural global surface coordinate system. The global surface coordinate system enables the position of any surface point to be specified as a set of numerical values, such as a pair of coordinates values (u,v).
The mathematics defining other types of surfaces do not include a global surface coordinate system. For these surfaces, there is no coordinate system within or on the surface itself that can define the position of any surface point as a set of numerical values. Examples of these types of surfaces include subdivision surfaces, implicit surfaces, and fractal surfaces.
Subdivision surfaces can create piecewise smooth surfaces out of arbitrary meshes of points. From an initial mesh of points, additional sets of points are added to provide additional surface detail and form a smoother surface, in a process referred to as refinement. The repeated application of refinement operations produces a hierarchy of progressively more detailed meshes, which ultimately converge at its limit to a subdivision surface. There are numerous subdivision surface refinement schemes that are well known in the art. Subdivision surfaces have many advantages in modeling three-dimensional objects, including modeling piecewise smooth surfaces of arbitrary topology and sharp features, edges, creases, and corners. However, because the surface is the result of the progressive refinement of a set of arbitrary meshes, there is no single surface coordinate system, or coordinate system located within the subdivision surface, that can specify the location of any given point on the subdivision surface.
Implicit surfaces are surfaces defined by an isosurface of a function of three or more dimensions. An isosurface is the set of function solutions having a constant, specified value. For example, if a function defines the pressure of fluid in a three-dimensional flow, an implicit surface can be specified as the set of function values in the three-dimensional flow having a given pressure value. Other types of functions can be used to define implicit surfaces, including the signed distance function often used to define level sets. With implicit surfaces, the implicit surface is deduced from the output of a more complex function of three or more dimensions. Because there is no explicit mathematical equation defining the implicit surface itself, there is no surface coordinate system, or coordinate system within the implicit surface, that can specify the location of any given point on the implicit surface.
Because some types of surfaces, including but not limited to subdivision surfaces, implicit surfaces, and fractal surfaces, do not have a natural global surface coordinate system, which is a coordinate system within or on the surface that is capable of specifying the location of any point on the surface as a set of numerical values, other techniques must be used to evaluate surface attribute functions.
For example, the position of a surface point can be determined in three-dimensional space. Using this three-dimensional position of a surface point, the surface attribute functions can be evaluated to determine the surface attribute values. Even if the attribute values are fixed to the surface, the surface attribute functions for a point on the surface must be evaluated repeatedly because the position of a surface point in three-dimensional space changes as the surface's pose changes, even if the relative location of the surface point within a surface remains unchanged. Additionally, surfaces are often sampled at a rate based on the viewpoint or camera parameters used to render a scene. As the camera or viewpoint changes, the surface points that are sampled and hence evaluated by surface attribute functions change as well. Thus, it is difficult to cache attributes of surface points for these surface types.
One prior approach caches surface attribute values for surfaces without global surface coordinate systems in a three dimensional data structure. In this approach, a data structure such as a voxel grid or brick map stores surface attribute values at the three-dimensional locations corresponding with the locations of their associated surface points. The three-dimensional data structures include significant amounts of empty space, corresponding to the three-dimensional space not occupied by the surface of an object. Even with compression schemes, these data structures require enormous amounts of memory and are difficult to use effectively.
Altasing is another prior approach that attempts to superimpose or project a global surface coordinate system over multiple surfaces that do not have their own surface coordinate system. The global coordinate system provided by atlasing schemes behaves poorly for complex surface topologies and at the seams between surfaces, having numerous gaps, discontinuities, and inconsistencies.
It is therefore desirable for a system and method to enable caching of surface attribute values for surfaces without global surface coordinate systems. It is further desirable for the system and method to enable the retrieval of cached surface attribute values without reevaluating surface attribute functions. It is further desirable for the system and method to efficiently store cached surface attribute values with minimal wasted memory.